package demo.src;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

import demo.src.MazeGenerate;
import javafx.scene.effect.Light.Point;

/**
 * A星算法类
 */
public class AStar {
    /** 方向 **/
    private int[][] directions;
    /**
     * 内部类，坐标
     * <p> 坐标-{@link #x}
     * <p> y坐标-{@link #y}
     * <p> 信息值-{@link #prefix}
     */
    private class Point{
        int x;
        int y;
        int prefix;

        /**
         * @param x x坐标
         * @param y y坐标
         * @param prefix 信息值
         */
        Point(int x,int y,int prefix){
            this.x=x;
            this.y=y;
            this.prefix=prefix;
        }
        //重写hashCode和equals方法（常规操作）
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + getEnclosingInstance().hashCode();
            result = prime * result + x;
            result = prime * result + y;
            return result;
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Point other = (Point) obj;
            if (!getEnclosingInstance().equals(other.getEnclosingInstance()))
                return false;
            if (x != other.x)
                return false;
            if (y != other.y)
                return false;
            return true;
        }
        /** 获取A星单例模式对象，用于内部使用 **/
        private AStar getEnclosingInstance() {
            return AStar.this;
        }
    }

    /**
     * 内部类--路径链表
     * <p> 前置节点-{@link #pre}
     * <p> 当前节点-{@link #curr}
     */
    class Link{
        Link pre;
        AStar.Point curr;

        /**
         * 路径集
         * <p> 采用前置链表主要为了路径搜索时更便捷
         * @param pre 前置节点
         * @param curr 当前节点
         */
        public Link(AStar.Link pre, AStar.Point curr) {
            this.pre = pre;
            this.curr = curr;
        }
        
    }
    /** 单例模式对象A星算法 **/
    private volatile static AStar aStar;
    private AStar(){
        //初始化方向
        this.directions=new int[][]{
            {-1,-1},{-1,0},{-1,1},
            {0,-1},        {0,1},
            {1,-1}, {1,0}, {1,1}
        };
    }

    /**
     * 单例模式
     * @return 自身对象
     */
    public static AStar getAStar() {
        if (aStar == null) {  
            synchronized (MazeGenerate.class) {
                if (aStar == null) {
                    aStar = new AStar();
                }
            } 
        } 
        return aStar;  
    }

    /**
     * 寻找迷宫路径
     * @param maze 二维字符数组表示的迷宫，其中 '■' 表示墙壁，其他字符表示可通行区域
     * @return 一个包含 int[] 数组的列表，表示从起点到终点的路径，如果找不到路径，则返回空列表
     */
    public List<int[]> search(char[][] maze) {
        // 创建一个优先级队列用于存储当前遍历节点的链表，按照节点的前缀距离进行排序
        Queue<Link> open = new PriorityQueue<Link>(
                (a, b) -> (a.curr.prefix - b.curr.prefix)
        );

        // 创建一个 HashMap 用于存储已经遍历过的节点及其前缀距离
        Map<Point, Integer> close = new HashMap<Point, Integer>();

        // 初始化存储最终路径的变量为 null
        Link ans = null;

        // 定义起点，并将其加入 open 队列和 close 集合
        Point start = new Point(0, 0, 0);
        open.offer(new Link(null, start));
        close.put(start, start.prefix);

        // 使用广度优先搜索（BFS）遍历迷宫，寻找最短路径
        while (!open.isEmpty()) {
            Link link = open.poll();
            Point curr = link.curr;

            // 当前节点为终点时，表示已经找到了一条路径，记录该路径，并结束循环
            if (curr.x == maze.length - 1 && curr.y == maze[0].length - 1) {
                ans = link;
                break;
            }

            // 在四个方向上尝试移动
            for (int[] direction : directions) {
                int nextX = curr.x + direction[0];
                int nextY = curr.y + direction[1];
                Point next = new Point(nextX, nextY, curr.prefix + 1);

                // 判断下一个位置是否在迷宫范围内，且是可通行的，并且没有被遍历过或者新的路径更短
                if (nextX >= 0 && nextX < maze.length
                        && nextY >= 0 && nextY < maze[0].length
                        && maze[nextX][nextY] != '■'
                        && close.getOrDefault(next, Integer.MAX_VALUE >> 1) > next.prefix) {
                    // 将新节点加入到 open 队列和 close 集合中
                    open.offer(new Link(link, next));
                    close.put(next, next.prefix);
                }
            }
        }

        // 根据最终找到的路径链表 ans，构建最终的结果列表
        List<int[]> res = new ArrayList<int[]>();
        if (ans != null) {
            while (ans != null) {
                Point curr = ans.curr;
                // 将路径上的点标记为 '*'，表示为路径上的点
                maze[curr.x][curr.y] = '*';
                res.add(new int[]{curr.x, curr.y});
                ans = ans.pre;
            }
        }

        // 将结果列表反转，使得路径的顺序正确
        Collections.reverse(res);

        // 返回最终的路径结果
        return res;
    }
}
